1. Field of the Invention
The present invention pertains generally to error detection/correction and more particularly to systems and methods used in Reed-Solomon (RS) coding and decoding for error correction.
2. Description of Related Art
Digital processing has become pervasive in modern society. For example, digital processing circuitry is commonly employed in many modern products, including personal computers, automobiles, communications equipment, and common household devices. One advantage of digital processing circuitry is that it can perform complex operations at rapid speeds, which has allowed activities previously considered impractical to be readily implemented. A familiar example of a digital processing system is a compact disc system reading digital data from a digital compact disc.
The communication of digital data is often a crucial component of digital processing systems. Typically, data is read from or written to local or remote data storage locations in successive read and write operations across a communications link. In such data storage locations, data is preferably stored as binary digits called "bits". In the example of a compact disc system, bit data is generally read from the compact disc and communicated among internal or external components, such as a microprocessor or a digital sound card in a personal computer.
FIG. 1A illustrates an overview of a digital processing system including an RS encoder 150, a communication channel or storage medium 152, and an RS decoder 154. An original data message is received from a data source 158, encoded by the RS encoder 150 and transferred over a communication channel 152 or stored in storage medium 152. The RS decoder 154 receives or reads the transferred data and decodes it to extract the original data message before sending the original data message to the data receiver 160. As shown in FIG. 1A, errors 156 are sometimes introduced during the transfer of the data bits as a result of, for example, channel distortion or noise. Errors 156 can also be introduced by defects of the data storage locations at which the data is stored. Such errors are typically rare in relation to the total amount of data transferred correctly. In some systems, however, a particular kind of data error, called a "burst error", occurs in consecutive data bits. Burst errors are often caused on compact discs, for example, by scratches, fingerprints, or other physical defects on the disc.
Consequently, to ensure data integrity within the system (i.e., to produce correct results), data errors must be detected and corrected. To facilitate error detection and correction of the data, encoding techniques are often used to encode the data prior to its transfer or storage. By encoding the data, redundancies are introduced upon the data. Typically, encoding is accomplished by dividing the message data word by a generating polynomial and appending the remainder to the message data. Such redundancies increase the likelihood that the data can be recovered even if errors are introduced into the data during its transfer. Once transferred, the encoded data is thereafter decoded to recreate the original (i.e., pre-encoding and transfer) data values.
Various coding schemes have been developed and are commonly used in digital processing and communication devices. Industry-wide standards have been set forth for coding and error correction schemes to provide intercompatibility of products and devices constructed by different manufacturers. Standards have been set forth, for instance, for the encoding of data stored on optical storage devices, such as CD-ROM storage devices.
Reed-Solomon (RS) coding is exemplary of a coding scheme typically utilized to encode digital data. Error-correction operations, however, are computationally intensive, and as products and systems emerge in which data is transferred at quicker rates, the rates at which error-correction operations must be performed must be increased correspondingly. Likewise, higher density semiconductor technologies and the faster transfer rates increase the possibility of errors and, therefore, necessitate more robust error detection and correction. When more powerful RS codes are employed (e.g., those capable of correcting three or more burst errors), the decoding algorithm becomes difficult to solve using only algebraic methods. The first part of a standard decoding algorithm, for example, calculates the partial syndromes of a codeword and converts them into the coefficients (i.e., .LAMBDA..sub.n) of an error-locator polynomial .LAMBDA.(x), which has the property that its roots correspond directly to the location of the errors in the codeword. A partial syndrome is calculated by dividing a polynomial representing the received codeword by a factor of the generating polynomial. The remainder of this division operation is a partial syndrome. The second part of a decoding algorithm is to determine the roots of the error locator polynomial. For error-locator polynomials of small degree, the roots can be reasonably calculated algebraically. For error locator polynomials of high degree, however, a brute force method is preferably employed to evaluate the polynomial with every possible root value and determine which roots produce a zero result (where a zero result indicates a error location).
For these more powerful codes, a decoding algorithm may employ a method known as a Chien Search. Because the Chien Search must test every possible value, it is often the most time consuming and computationally intensive part of the decoding algorithm. Therefore, it is advantageous to perform the Chien Search in parallel to reduce the execution time for error correction. In prior designs, this parallelism was achieved by merely replicating serial Chien Search logic and parceling out portions of the search to each parallel module. The technique, however, is costly because the replication requires a significant number of logic gates. As such, need exists for a less costly design for implementing a parallel Chien Search.